package 并查集;

public class UnionFind {

    private int[] parents;
    private int count;//辅助属性

    public UnionFind(int size){
        parents=new int[size];
        this.count=size;
        for (int i = 0; i < size; i++) {
            this.parents[i]=i;//开始时每个元素的父集都是自己
        }
    }

    public void union(int kid,int parent){
        int kidId = find(kid);
        int parentId = find(parent);
        if(kidId==parentId)
            return;
        count--;
        parents[kidId]=parentId;
    }

    //查找父集
    public int find(int p){
        while (p!=parents[p]){
            parents[p]=parents[parents[p]];
            p=parents[p];
        }
        return p;
    }

    public boolean isConnected(int p,int q){
        return find(p)==find(q);
    }

    public int getCount(){
        return this.count;
    }

}
